#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

namespace std {
    class Read {
        public:
            template<typename T>
            inline Read & operator >> (T & x) {
                T sum = 0, opt = 1;
                char ch = getchar();
                while(!isdigit(ch)) opt = (ch == '-') ? -1 : 1, ch = getchar();
                while( isdigit(ch)) sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
                x = sum * opt; return *this;
            }
    };
}
#define int long long
#define all(a) a.begin(), a.end()

using namespace std; Read fin;

const int INF = 0x3f3f3f3f3f3f3f3f;

vector<int> arr;
int n;

int res;

void dfs(int u, int last_0, int last_1, int sum) {
    if (u == n) {
        res = max(res, sum);
        return ;
    }

    // TODO: 0

    if (last_0 == arr[u])
        sum += arr[u];

    dfs(u + 1, arr[u], last_1, sum);

    if (last_0 == arr[u])
        sum -= arr[u];

    // TODO: 1

    if (last_1 == arr[u])
        sum += arr[u];
    
    dfs(u + 1, last_0, arr[u], sum);

    if (last_1 == arr[u])
        sum -= arr[u];

    return ;
}

void solve() {
    fin >> n;
    if (n <= 30) {
        arr.resize(n);
        res = 0;

        for (int i = 0; i < n; i ++ )
            fin >> arr[i];
        
        dfs(0, -1, -1, 0);

        cout << res << endl;
    } else {
        puts("0");
    }

    return ;
}

signed main() {
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    int T; fin >> T;
    while(T -- ) {
        solve();
    }
    return 0;
}